/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

                For example,
                Given n = 3, there are a total of 5 unique BST's.
                
                   1         3     3      2      1
                    \       /     /      / \      \
                     3     2     1      1   3      2
                    /     /       \                 \
                   2     1         2                 3
 */
public class UniqueBinarySearchTrees {

	public int numTrees(int n) {
		return numTrees(1, n);
	}

	private int numTrees(int start, int end) {
		if (start >= end)
			return 1;

		int total = 0;
		for (int i = start; i <= end; i++) {
			total += numTrees(start, i - 1) * numTrees(i + 1, end);
		}

		return total;
	}

	@Test
	public void test() {
		assert numTrees(3) == 5;
		assert numTrees(4) == 14;
    }
}
